package com.example.linked;

/**
 * 给你两个二进制字符串，返回它们的和（用二进制表示）
 */
public class Leecode67_addBinary {

    public static void main(String[] args) {

        System.out.println(addBinary1("1100", "100110"));
        System.out.println(addBinary2("1100", "100110"));
    }

    /**
     * 解法一:使用链表
     * 1.两个二进制字符串转成链表
     * 2.遍历两个链表，并将两个链表的各个位对应相加结果形成新的链表
     *  ⼤大于2，则进位，将进位加到下个节点
     * 3.将结果链表拼成二进制字符串返回
     *
     * 边界问题
     *   两个链表边界：next==null
     * 细节问题
     *    二进制字符串转链表时用头插法(方便后面直接从头开始相加)
     *    结果链表用尾插法(不用在讲结果字符串进行翻转)
     *   两个链表⻓长度不不一致，短链表⾼高位视为0
     *   链表最⾼高位发⽣生进位，结果链表需要增加⼀一个节点存放进位数字
     *
     * @param a 二进制字符串1
     * @param b 二进制字符串2
     * @return 结果二进制字符
     */
    public static String addBinary1(String a, String b) {
        if (a.length() == 0 || b.length() == 0 || a == null || b == null) {
            return "";
        }
        ListNode binaryHead1 = new ListNode(-1);
        ListNode curBin1 = binaryHead1;
        ListNode binaryHead2 = new ListNode(-1);
        ListNode curBin2;
        curBin2 = binaryHead2;
        ListNode resultHead = new ListNode(-1);
        ListNode resultCur = resultHead;
        int carry = 0;
        // 1.头插法将两个二进制字符串形成两个链表
        for (int i = 0; i < a.length(); i++) {
            ListNode tmp = new ListNode(a.charAt(i) - '0');
            tmp.next = binaryHead1.next;
            binaryHead1.next = tmp;
        }

        for (int i = 0; i < b.length(); i++) {
            ListNode tmp = new ListNode(b.charAt(i) - '0');
            tmp.next = binaryHead2.next;
            binaryHead2.next = tmp;
        }

        // 2.遍历两个链表，并将两个链表的各个位对应相加结果形成新的链表
//        int i = 1;
        while (curBin1.next != null || curBin2.next != null) {
            int x = curBin1.next != null ? curBin1.next.val : 0;
            int y = curBin2.next != null ? curBin2.next.val : 0;
            int sum = carry + x + y;
            carry = sum / 2;
            // 创建新节点
            ListNode resultTmp = new ListNode(sum % 2);
//            System.out.println("第" + i + "位进行运算: x:" + x + " y:" + y
//                    + " sum:" + sum + " carry:" + carry + " result:" + resultTmp.val);
            // 结果不用尾插法(因为尾插法，到最后还得颠倒一次)
            // 下面的代码是尾插发(即直接在最后插入)
//            resultCur.next = resultTmp;
//            resultCur = resultCur.next;
            // 结果用头插法插入
            resultTmp.next = resultHead.next;
            resultHead.next = resultTmp;
            // 向下移动两个二进制数字链表
            curBin1 = curBin1.next == null ? curBin1 : curBin1.next;
            curBin2 = curBin2.next == null ? curBin2 : curBin2.next;
//            i++;
        }

        // 最后单独处理末尾有进位的情况
        if (carry == 1) {
            System.out.println("最高位有进位");
            ListNode resultTmp = new ListNode(carry);
            // 结果不用头插法(因为头插法，到最后还得颠倒一次)
            resultTmp.next = resultHead.next;
            resultHead.next = resultTmp;
        }


//        curBin1 = binaryHead1;
//        while (curBin1.next != null) {
//            curBin1 = curBin1.next;
//            System.out.print(curBin1.val + "->");
//        }
//        System.out.println();
//
//        curBin2 = binaryHead2;
//        while (curBin2.next != null) {
//            curBin2 = curBin2.next;
//            System.out.print(curBin2.val + "->");
//        }
        // 3.将最后的结果拼成字符串返回
        resultCur = resultHead;
        StringBuffer sb = new StringBuffer();
        while (resultCur.next != null) {
            resultCur = resultCur.next;
            sb.append(resultCur.val);
//            System.out.print(resultCur.val + "->");
        }
//        System.out.println(sb);
        return sb.toString();
    }

    /**
     * 解法二:直接在原字符串上进行各位相加
     * 1.末尾对齐，逐位相加，逢二进一
     * 2.遍历两个字符串，从低位开始遍历相加，a、b中短的位置补0
     *  ⼤大于2，则进位，将进位加到下上一位
     * 3.将结果二进制字符串翻转后返回
     *
     * 边界问题
     * 细节问题
     *   两个二进制字符串⻓长度不不⼀致，短字符串⾼高位视为0
     *   最⾼高位发⽣生进位，结果需要增加一个字符存放进位数字
     *
     * @param a 二进制字符串1
     * @param b 二进制字符串2
     * @return 结果二进制字符
     */
    public static String addBinary2(String a, String b) {
        StringBuffer resultBuf = new StringBuffer();
        // 二进制相加，末尾对齐，逐位相加，逢二进一
        // carry表示上一位置的进位，初始为0
        int n = Math.max(a.length(), b.length()), carry = 0;
        // 从低位开始遍历相加，a、b中短的位置补0
        for (int i = 0; i < n; ++i) {
            int x = i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            int y = i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            int sum = x + y + carry;
            resultBuf.append(sum % 2);
            carry = sum / 2;
        }
        //进位有值，存入答案字符串中
        if (carry > 0) {
            resultBuf.append(1);
        }
        //最终将答案串反转并返回
        return resultBuf.reverse().toString();
    }

    private static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
}
